/*
https://leetcode.cn/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/solution/zui-duo-k-ci-jiao-huan-xiang-lin-shu-wei-hou-de-da/
 */
import java.util.LinkedList;
import java.util.Queue;

public class Solution1505 {

    static class BIT{
        int[] h;
        int n;

        public BIT(int n){
            h=new int[n+1];
            this.n=n;
        }

        int lowbit(int x){
            return x&(-x);
        }

        int query(int x){
            int t=0;
            while (x>0){
                t+=h[x];
                x-=lowbit(x);
            }
            return t;
        }

        void update(int x){
            while (x<=n){
                h[x]++;
                x+=lowbit(x);
            }
        }
    }

    public String minInteger(String num, int k) {
        Queue<Integer>[] pos=new Queue[10];
        for (int i=0;i<10;i++){
            pos[i]= new LinkedList<>();
        }
        for (int i=0;i<num.length();i++){
            pos[num.charAt(i)-'0'].offer(i+1);
        }
        StringBuilder stringBuilder=new StringBuilder();
        BIT bit=new BIT(num.length());
        for (int i=0;i<num.length();i++){
            for (int j=0;j<10;j++){
                if (!pos[j].isEmpty()){
                    int behind=bit.query(num.length())-bit.query(pos[j].peek());
                    int dis=pos[j].peek()+behind-(i+1);
                    if (dis<=k){
                        bit.update(pos[j].poll());
                        stringBuilder.append(j);
                        k-=dis;
                        break;
                    }
                }
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution1505().minInteger("9438957234785635408",23));
    }
}
